The technology described herein relates to the programming of flash memories, especially multi-bit-per-cell flash memories.
A simplified block diagram of a Multi-Bit-Per-Cell (MBPC) flash memory device 10 is shown in FIG. 1. Specifically, the two components of flash memory device 10 that are illustrated in FIG. 1 are a flash controller 12 and a flash memory cell array 18.
Flash controller 12 includes two blocks: an encoder block 14 that translates a stream of information bits that the user wishes to store in flash cell array 18 into a stream of states or voltage levels that should be programmed into the cells of flash cell array 18, and a decoder block 16 that translates a stream of cell states or voltage levels read from flash cell array 18 into the stream of information bits that was stored in flash cell array 18.
The cost of a MBPC Flash system is mainly influenced by the size of the flash memory cell array required in order to store a given amount of information, i.e., the number of flash cells required in order to store a given amount of information. It is convenient to use the number of information bits per flash cell (abbreviated as IBPC) as a normalized measure of the flash memory's cost efficiency:IBPC=(number of information bits stored in the flash memory)÷(number of cells in the flash memory)
One might argue that the IBPC of a MBPC Flash system can be increased simply by increasing the number of states or voltage levels that can be programmed in a flash cell. However a fair comparison should also take into account the MBPC flash reliability and the MBPC flash performance.
The main criterion of flash reliability is the ability of the controller to recover the stored information with high probability, i.e. with a negligible bit error rate. The states or voltage levels that are programmed into the flash cells are not always equal to the states or voltage levels that are read from the flash cells. This is due to physical processes that occur inside the flash cell array that cause the charge stored in the flash cell to change. These harmful physical processes corrupt the information stored in the flash cells. Usually the flash reliability is a function of time and flash cell wear level. The flash reliability is determined primarily by the following factors:                1. Data retention: the expected amount of time that data can be stored in the flash cells and still be recovered with high reliability.        2. Program/Erase cycles: the expected number of times that the flash cells can be programmed and erased while allowing reliable storage of data.        
The main criterion of flash performance is the flash read/write throughput, i.e. the throughput of writing data to the flash memory and reading data from the flash memory, measured in information bits per second.
Unfortunately, increasing the number of voltage levels that can be programmed in each flash cell has a negative effect both on the flash memory reliability and on the flash memory performance. For example, as the number of voltage levels increases, the expected data retention time of the flash memory decreases and the expected number of available program/erase cycles decreases, resulting in a lower flash memory reliability. Moreover, the read/write throughput of the flash memory becomes slower with the increase of the number of flash cell voltage levels. Hence there is a tradeoff between the flash memory cost (the IBPC of the flash memory) and the reliability and performance of the flash memory. Obviously, one wishes to optimize this tradeoff. This can be done through an appropriate design of the flash controller.
A simple conventional flash controller uses a bijective mapping, i.e. a mapping that is one-to-one and onto, in order to directly map k information bits into a state or voltage level out of q=2k states of each flash cell. By allowing only a small number of states q to be programmed in a cell, the probability of the cell to make a transition out of its state is made negligible, providing a reliable flash memory device. Note that such a flash memory device can use only a number of states q in the cell that is a power of 2 because bits are directly mapped to cell states through a bijective mapping.
U.S. Pat. No. 6,847,550, issued Jan. 25, 2005 to Park and entitled “NONVOLATILE SEMICONDUCTOR MEMORY HAVING THREE_LEVEL MEMORY CELLS AND PROGRAM AND READ MAPPING CIRCUITS THERFOR” (hereinafter “Park '550”), describes a method of trading-off Flash cost and reliability by using a non-bijective mapping, that is one-to-one but not onto, from information bits to the states of one or more flash cells. By using the non-bijective mapping, a number of cell states that is not a power of 2 can be used. In the example described in Park '550, three-state cells are used. This provides higher flash reliability compared to a flash memory device based on four-state cells (due to lower transition probability from state to state) and lower cost compared to a flash memory device based on two-state cells.
U.S. Pat. No. 6,469,931, issued Oct. 22, 2002 to Ban et al. entitled “METHOD FOR INCREASING INFORMATION CONTENT IN A COMPUTER MEMORY” (hereinafter “Ban '931”), provides a general framework for reducing the cost of a flash memory device while maintaining the reliability of the flash memory device. This is done by mapping large blocks of K information bits into large blocks of M cells with q states. The encoder block (e.g. encoder block 14 of FIG. 1) implements a mapping function, also known as an Error Correcting Code (ECC), that maps points from the vector space 2K onto points in the vector space qM. The mapping is not onto, i.e., not all configurations of cell states are used (2K<qM). The decoder block (e.g. decoder block 16 of FIG. 1) collectively decodes the M read cell states and determines the most probable legitimate configuration of cell states that was stored in the flash memory, which is then used for recovering the K stored information bits. It is well known from information theory and coding theory (R. Gallagher, Information Theory and Reliable Communication, Wiley, New York N.Y. USA, 1971) that increasing the dimensionality of the space of possible cell state configurations to which a block of information bits is mapped allows for more efficient storage of information. This way, if a good mapping function or ECC is used, more information bits can be mapped across a given number of flash cells, while the probability of the flash memory to make a transition from one legitimate configuration of states to another is kept arbitrarily small. However, it is not sufficient that the mapping function provide for a high IBPC. The mapping function should also allow low complexity implementation of the encoder and decoder blocks. Coding theory (S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications, Prentice Hall, Englewood Cliffs N.J. USA, 1983) provides a theoretical basis for designing such good ECCs.
In the example provided in Ban '931, a direct mapping function is used for mapping information bits into configurations of cell states. This method incurs high encoder complexity. A more common low complexity approach, shown in FIG. 2, is to divide encoder block 14 into two parts: 1) a binary ECC encoder block 20 that maps K information bits into N coded bits by adding N-K redundant bits and 2) a simple mapper block 22 that implements a one-dimensional bijective mapping function that maps the N coded bits into M cells by mapping each N/M bits into one of the q=2N/M states of a cell.
Decoder block 16 is also divided similarly into two parts: 1) a simple demapper block 24 that implements a one-dimensional bijective mapping function that maps the M read cell states into N bits by mapping each read cell state into N/M bits, and 2) an ECC decoder block 26 that decodes the N “noisy” bits received from demapper 24 and produces an estimation of the K information bits. An optimal decoder 26 returns the most probable K information bits given the N “noisy” bits.